#include <mips/regdef.h>

.data
a:
	.word	701, 301, 132, 57, 23, 10, 4, 1
	
SEQUENCESIZE:
	.word	8

.text
.globl	shellsort
.ent	shellsort

shellsort:						# void shellsort (char **words, int arraysize)
	.frame		$fp,88,ra		# Definicion de stack frame
	subu		sp,sp,88		# Creo el stack frame
	.cprestore	72
	sw			ra,80(sp)		# Guardo ra
	sw			$fp,76(sp)		# Guardo fp
	sw			gp,72(sp)		# Guardo gp
	move		$fp,sp			# fp=sp

	sw			a0,88($fp)		# Guardo el argumento 0 (**words)
	sw			a1,92($fp)		# Guardo el argumento 1 (arraysize)

	sw			zero,16($fp)	# i=0
	sw			zero,20($fp)	# j=0
	sw			zero,24($fp)	# k=0
	sw			zero,28($fp)	# gap=0
	lw			t0,a
	sw			t0,32($fp)		# a[0]=701
	lw			t0,a+4
	sw			t0,36($fp)		# a[1]=301
	lw			t0,a+8
	sw			t0,40($fp)		# a[2]=132
	lw			t0,a+12
	sw			t0,44($fp)		# a[3]=57
	lw			t0,a+16
	sw			t0,48($fp)		# a[4]=23
	lw			t0,a+20
	sw			t0,52($fp)		# a[5]=10
	lw			t0,a+24
	sw			t0,56($fp)		# a[6]=4
	lw			t0,a+28
	sw			t0,60($fp)		# a[7]=1
	sw			zero,64($fp)	# x=NULL

	sw			zero,24($fp)	# k=0
	lw			s0,24($fp)		# s0=k=0
	lw			s6,SEQUENCESIZE # s6=SEQUENCESIZE
for_k:							# For sequencias
	subu		t2,s0,s6		#Evaluo s0-t1 y guardo en t2
	beqz		t2,fin_shellsort	#Si se cumple la condicion (t0=t1=SEQUENCESIZE) salgo del FOR
	
	sll			t2,s0,2			# t2=k*4
	addiu		t2,32			# Al numero que calcule en el paso anterior le sumo la posicion de a[0] en el stack
	addu		t2,t2,$fp		# Sumo en t2 el fp para tener la posicion de memoria de a[k]					
	lw			s1,0(t2)		# s1=a[k]
	sw			s1,28($fp)		# s1=gap=a[k]

	move		s2,s1			# s2=i=gap
	sw			s2,16($fp)		# i=gap
	lw			s3,92($fp)		# s3=arraysize
for_i:							# For palabras
	subu		t3,s2,s3		# Evaluo s2-s3 y guardo en t3
	bgez		t3,fin_for_i	# Si se cumple la condicion (s2=s3=arraysize) salgo del FOR
	
	lw			t2,88($fp)		# t2=words
	sll			t3,s2,2			# t3=4*(i)
	addu		t3,t3,t2		# Desplazo words en 4*i para tener la posicion de memoria de words[i]
	lw			t4,0(t3)		# t4=words[i]
	sw			t4,64($fp)		# x=words[i]
	
	subu		s5,s2,s1		# i-gap
	sw			s5,16($fp)		# j=i-gap
for_j:							# For intercambio
	bltz		s5,fin_for_j	# j<0
	
	lw			t2,88($fp)		# t2=words
	sll			t3,s5,2			# t3=4*(j)
	addu		t3,t3,t2		# Desplazo words en 4*j para tener la posicion de memoria de words[j]
	lw			a0,0(t3)		# a0=words[j]
	lw			a1,64($fp)		# a1=x
	la			t9,strcmp		# Cargamos en t9 la referencia a strcasecmp
	jal			ra,t9			# Llamamos a strcasecmp
	blez		v0,fin_for_j	# strcasecmp(words[j],x)<=0	
		
	lw			t2,88($fp)		# t2=words
	addu		t3,s5,s1		# t3=j+gap
	sll			t4,t3,2			# t4=4*(j+gap)
	addu		t5,t2,t4		# t5=words[j+gap]
	
	sll			t3,s5,2			# t3=4*(j)
	addu		t3,t2,t3		# Desplazo words en 4*j para tener la posicion de memoria de words[j]
	lw			t4,0(t3)		# t4=*words[j]

	sw			t4,0(t5)		# words[j+gap]=words[j]

	subu		s5,s5,s1		# j=j-gap
	sw			s5,20($fp)		# Actualizo el valor de j
	b			for_j			# Sigo iterando

fin_for_j:
	lw			t2,88($fp)		# t2=words
	addu		t3,s5,s1		# t3=j+gap
	sll			t4,t3,2			# t4=4*(j+gap)
	addu		t5,t2,t4		# t5=words[j+gap]

	lw			t4,64($fp)		# t4=x
	sw			t4,0(t5)		# words[j+gap]=x;

	addiu		s2,1			# s2=i++
	sw			s2,16($fp)		# Actualizo el valor de i
	b			for_i			# Sigo iterando

fin_for_i:
	addiu		s0,1			# t0=k++
	sw			s0,24($fp)		# Actualizo el valor de k
	b			for_k			# Sigo iterando
		
fin_shellsort:					# Fin de la funcion
	move		sp,$fp			# sp=fp
	lw			ra,80(sp)		# Restauro ra
	lw			$fp,76(sp)		# Restauro fp
	lw			gp,72(sp)		# Restauro gp
	addu		sp,sp,88		# Elimino el stack frame
	j			ra				# Retorno a funcion llamadora

.end	shellsort
